package Hard;

// 10.正则表达式匹配
// 特别注意：.*的情况
// 难点: "aaa"和"a*a" 应该返回true
// 注意: 子串中也可能存在.*或A*的匹配问题
public class Solution10 {
    public static boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        //s里只有0个或1个字符的情况
        if (s.equals(p) || ((s.length() == 1 && p.length() == 1) && (p.equals("."))))
            return true;
        else if (s.length() == 1 && p.length() == 1)
            return false;
        //拿p去匹配s
        try {
            while (i < s.length()) {
                if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                    //需要注意.*的情况
                    if (p.charAt(j) == '.') {
                        // 思路:遇到.*时直接寻找从下标i开始，是否存在子串str，使得str==p.substring(j+2,p.length())
                        // 注意:子串中也可能存在.*或A*的匹配问题
                        for (int k = i; k < s.length(); k++) {
                            //if(s.substring(i,s.length()).equals(p.substring(j+2,p.length())))
                            //  return true;
                            if (isMatch(s.substring(k, s.length()),p.substring(j + 2, p.length())))
                                return true;
                        }

                        i=s.length();
                        j+=2;
                        break;

                    }
                    // 错误思路: 没有考虑到aaa和a*a的情况
                    while (i < s.length() && s.charAt(i) == p.charAt(j)) { // 考虑到aa和a*的情况，这里需要注意i不能超过length
                        if(isMatch(s.substring(i,s.length()),p.substring(j+2,p.length())))
                            return true;
                        i++;
                    }
                    j += 2;
                } else if (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j)) {
                    i++;
                    j++;
                } else
                    return false;
            }
        } catch (StringIndexOutOfBoundsException e) {
            return false;
        }

        // s遍历完以后看看p后面还有没有字符，除非p剩余字符是A*的情况，否则返回false，A为任意字符
        // 不能写进finally里

        //错误思路:最后不能只考虑 ""和"a*"的情况，而且要考虑""和"a*a*"的情况
        if (j == p.length())
            return true;
        while(j+1<p.length() && p.charAt(j + 1) == '*'){
             j+=2;
        }
        if(j==p.length())
            return true;
        return false;

    }

    public static void main(String[] args) {
        System.out.println(isMatch("ab", ".*c"));
    }
}